/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithm;

/**
 *
 * @author Winzelric
 */
public class KnuthMorrisPrat {

  public static int[] computePrefix(char[] w) {
    int[] t = new int[w.length];
    int i = 2, j = 0;
    t[0] = -1;
    if (t.length > 1) {
      t[1] = 0;
    }
    while (i < w.length) {
      if (w[i - 1] == w[j]) {
        t[i] = j + 1;
        j++;
        i++;
      } else if (j > 0) {
        j = t[j];
      } else {
        t[i] = 0;
        i++;
        j = 0;
      }
    }
    return t;
  }

  public static boolean kmp(String text, String pattern) {
    int[] arr = computePrefix(pattern.toCharArray());
    int n = text.length(), m = pattern.length();
    int i = 0, j = 0;
    while (i < n) {
      if (text.charAt(i) == pattern.charAt(j)) {
        if (j == m - 1) {
          return true;
        }
        i++;
        j++;
      } else if (j > 0) {
        j = arr[j - 1];
      } else {
        i++;
      }
    }
    return false;
  }
}
